package test;

import java.util.Arrays;
import java.util.Random;

/**
 * @ClassName Sort
 * @Description 十大排序
 * @Author ZJX
 * @Date 2024/7/23 18:49
 * @Version 1.0
 */
public class Sort {

    /*
     * @param arr: 
      * @return void 
     * @author: ZJX
     * @description: 冒泡排序 时间复杂度为O(N^2) 稳定的
     * @date: 2024/7/31 15:31
     */
    public void bubbleSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n-1; i++) { // 遍历 n - 1 次 因为单独一个元素即为有序
            for (int j = 0; j < n-1-i; j++) {
                if (arr[j] > arr[j+1]){
                   swap(arr,j,j+1);
                }
            }
        }
    }

    /*
     * @param arr:
      * @return void
     * @author: ZJX
     * @description: 选择排序 时间复杂度为O(N^2) 稳定的
     * @date: 2024/7/31 15:42
     */
    public void selectionSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n-1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]){
                    minIndex = j;
                }
            }
            swap(arr,i,minIndex);
        }
    }

    /*
     * @param arr:
      * @return void
     * @author: ZJX
     * @description: 双向选择排序
     * @date: 2024/8/3 9:12
     */
    public void bidirectionalSelectionSort(int[] arr) {
        int left = 0;
        int right = arr.length-1;
        while(left < right){
            int minIndex = left;
            int maxIndex = right;
            for (int i = left; i <= right; i++) {
                if (arr[i] < arr[minIndex]){
                    minIndex = i;
                }
                if (arr[i] > arr[maxIndex]){
                    maxIndex = i;
                }
            }

            swap(arr,left,minIndex);

            // 如果 maxIndex 是 left，则最大值已被交换到 minIndex 位置
            if (maxIndex == left) {
                maxIndex = minIndex;
            }

            swap(arr,right,maxIndex);
            left++;
            right--;
        }
    }

    /*
     * @param arr:
      * @return void
     * @author: ZJX
     * @description: 插入排序 时间复杂度为O(N^2) 稳定的
     *  插入排序:  数据越有序 排序越快
     * @date: 2024/7/31 15:47
     */
    public void insertionSort(int[] arr) {
        printArray(arr);
        for (int i = 1; i < arr.length; i++) {
            int key = arr[i];
            int j = i - 1;  // j 应该从 i-1 开始

            // 将大于 key 的元素向右移动
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
            printArray(arr);
        }
    }

    /*
     * @param num:
    	 * @param s:
    	 * @param e:
      * @return int
     * @author: ZJX
     * @description: 递归法求数组最大值
     * @date: 2024/7/25 14:02
     */
    public static int find(int[] num,int s, int e){
        if (s == e){
            return num[s];
        }
        int mid = s+(e-s)/2;
        int i1 = find(num, s, mid);
        int i = find(num, mid + 1, e);
        return Math.max(i,i1);
    }

    /*
     * @param arr:
      * @return void
     * @author: ZJX
     * @description: 堆排序  从小到大排序 利用大根堆 时间复杂度为 O(N*logN)
     * @date: 2024/7/31 8:46
     */
    public void heapSort(int[] arr){
//        创建大根堆
        for (int parent = (arr.length-1-1)/2; parent >= 0; parent--) {
            heapifyDown(arr, parent, arr.length - 1);
        }
        int end = arr.length - 1;
        while(end > 0){
            swap(arr,0,end);
            heapifyDown(arr,0,end-1);
            end--;
        }
    }

    private void heapifyDown(int[] arr, int parent, int end) {
        int leftChild = 2 * parent + 1;
        int rightChild = 2 * parent + 2;
        int largest = parent;

        if (leftChild <= end && arr[leftChild] > arr[largest]){
            largest = leftChild;
        }

        if (rightChild <= end && arr[rightChild] > arr[largest]){
            largest = rightChild;
        }

        if (largest != parent){
            swap(arr,parent,largest);
            heapifyDown(arr,largest,end);
        }
    }

    private void swap(int[] arr,int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }


    public void printArray(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n; ++i)
            System.out.print(arr[i] + " ");
        System.out.println();
    }

    /*
     * @param arr:
      * @return void
     * @author: ZJX
     * @description:  希尔排序 缩小增量排序 插入排序的优化 根据所选择的 增量序列 来决定
     *              通过逐步缩小的增量（gap）对元素进行分组，并在每个分组内进行插入排序
     *                  不稳定的排序
     * @date: 2024/8/2 18:00
     */
    public void shellSort(int[] arr) {
        int gap = arr.length;
        while(gap > 1){
            gap /= 2;  // 确保 gap 至少为 1
            shell(arr,gap);
        }
    }

    /*
     * @param arr:
    	 * @param gap:
      * @return void
     * @author: ZJX
     * @description: 对数组进行插入排序，使用当前的 gap 将元素分组。
     * @date: 2024/8/2 18:20
     */
    private void shell(int[] arr, int gap) {
         for (int i = gap; i < arr.length; i++) {
            int key = arr[i]; // 当前需要插入的元素
            int j = i - gap;  // 从当前元素的前一个间隔位置开始

            // 将当前元素插入到它的合适位置
            while (j >= 0 && arr[j] > key) {
                arr[j + gap] = arr[j]; // 将较大的元素向后移动一个间隔
                j -= gap; // 向前继续比较
            }
            arr[j + gap] = key; // 将当前元素放到正确位置
        }

    }
    /*
     * @param nums:
      * @return int[]
     * @author: ZJX
     * @description: 力扣 912 排序数组
     * @date: 2024/8/27 21:35
     */
    public int[] sortArray(int[] nums) {
        quickSort(nums,0,nums.length-1);
        return nums;
    }

    private void quickSort(int[] nums, int left, int right) {
//        选取基准值 分 左右两部分 然后 继续依次进行
//        基准值 可以选  第一个  最后一个  中间   随机(Random)

        if(left >= right){
            return;
        }

        int pivot = nums[left];
        int i = left;
        int j = right;

        while(i < j){
            while(i < j && nums[j] >= pivot){
                j--;
            }
//            走出循环说明 已经从右边找到第一个比基准元素小的数据了
            nums[i] = nums[j];

            while(i < j && nums[i] <= pivot){
                i++;
            }
//            走出循环 说明从左边找到了第一个比基准元素大的数据了
            nums[j] = nums[i];
        }

//        将基准元素放回原来位置
        nums[i] = pivot;

        quickSort(nums,left,i-1);
        quickSort(nums,i+1,right);
    }
}
